<?php 
/** 
 * 重建二叉树
 * 
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */

class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}

function reConstructBinaryTree($pre, $vin)
{
    // write code here
    if (isset($pre[0])) {
        $node = new TreeNode($pre[0]);
        //根节点在中序中的位置
        $vin_index = array_search($pre[0], $vin);
        //中序中的左孩子
        $vin_left = array_slice($vin, 0,$vin_index);
        //中序中的右孩子
        $vin_right = array_slice($vin, $vin_index + 1);

        //先序中的左孩子
        $pre_left = array_slice($pre, 1, $vin_index);
        //先序中的右孩子
        $pre_right = array_slice($pre, $vin_index + 1);
        
        
        $node->left = reConstructBinaryTree($pre_left, $vin_left);
        $node->right = reConstructBinaryTree($pre_right, $vin_right);
        return $node;
    }
    return null;
   
}

$pre = [1,2,4,7,3,5,6,8];
$vin = [4,7,2,1,5,3,8,6];
$node = reConstructBinaryTree($pre, $vin);
var_dump($node);
